// 把 0/1 转成 -1/+1，用前缀和相等来标记“0 和 1 数量相等”的区间
// 哈希表保存第一次出现的位置，即可在 O(n) 时间内求出最长长度
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int findMaxLength(int[] nums) {
        Map<Integer, Integer> hash = new HashMap<>();
        hash.put(0, -1); // 空数组和为0，位置记作-1

        int sum = 0, ret = 0;
        for(int i = 0; i < nums.length; i++) {
            sum += (nums[i] == 0 ? -1 : 1); // 0→-1，1→1
            if (hash.containsKey(sum)) {
                ret = Math.max(ret, i - hash.get(sum)); // 当前前缀和出现过，则中间子数组0和1数量相等
            } else {
                hash.put(sum, i); // 第一次出现该前缀和，记录位置
            }
        }
        return ret;
    }
}